package hot_problems_100;

import java.util.List;
import java.util.ArrayList;

public class P18_0054 {
    /*
    * 螺旋式地遍历一个矩阵，从左上角[0][0]开始，依次向右，向下，向左，向上地循环遍历，按遍历顺序返回一个List
    * */
    public List<Integer> spiralOrder(int[][] matrix) {
        // 0-右 1-下 2-左 3-上
        // n  m    n     n-1
        List<Integer> list = new ArrayList<>();
        int m = matrix.length, n=matrix[0].length;
        int min_x = 0, max_x = m-1, min_y = 0, max_y = n-1;
        int max_size = m * n;
        int x=0, y=0;
        int op = 0;
        list.add(matrix[0][0]);
        for(int k=0; k<max_size-1; k++){
            if(op==0){
                if(y<max_y){
                    y++;        // 右移
                } else {
                    min_x ++;   // 最小的行已经被遍历
                    op = 1;
                    x++;
                }
            } else if(op == 1){
                if(x<max_x){
                    x++;        // 下移
                } else {
                    max_y --;   // 最大的列已经被遍历
                    op = 2;
                    y--;
                }
            } else if(op == 2){
                if(y>min_y){
                    y--;        // 左移
                } else {
                    max_x --;   // 最大的行被遍历
                    op = 3;
                    x--;
                }
            } else {
                if(x>min_x){
                    x--;        // 上移
                } else {
                    min_y ++;
                    op = 0;
                    y++;
                }
            }

            list.add(matrix[x][y]);
        }
        return list;
    }
}
